1. Field of the Invention
The present invention generally relates to manufacturing resource planing, and more particularly to software systems for resource-constrained production planning.
2. Background Description
Software systems for resource-constrained production planning (RCPP) take as input data a description of a production planning problem. This includes a listing of the basic data objects of the problem; i.e., capacity resources, raw material resources, subassemblies, final products, and demands for the products, as well as a multi-level Bill-Of-Resources network that defines how the products can be produced from subassemblies, raw materials and capacities. It also includes various attributes on these objects such as supply volumes, demand volumes, production usage rates, and economic data or priorities. In addition, the problem data is defined with respect to a set of discrete time periods.
Given these inputs, an RCPP system computes a production plan that consists of two portions: (1) a production portion of plan that specifies of how much of each product is to be produced in each time period, and (2) a shipment portion of the plan that specifies how much of each demand is to be fulfilled in each time period. (The fulfillment of a demand in a period may be called a “shipment” to that demand.) The production plan computed by the RCPP system is normally required to be feasible, meaning it satisfies the resource constraints that are specified in the input data.
Two methods for solving the RCPP problem are described in U.S. Pat. No. 5,548,518 for “Allocation Method for Generating a Production Schedule” and U.S. Pat. No. 5,630,070 for “Optimization of Manufacturing Resource Planning”, both to Dietrich et al. More specifically, U.S. Pat. No. 5,548,518 discloses an allocation method which, in response to a specified requirement, determines what quantity of a product can be produced with a specified quantity of supply components, allocates a required quantity of supply components for filling a defined partial order and fills a remainder of the requirement at some later time. U.S. Pat. No. 5,630,070 discloses a method for constrained material requirements planning, optimal resource allocation and production planning which optimizes a manufacturing process by designating the amounts of various manufactured products to be produced, which products include both end products as well as subassemblies.
Users of RCPP systems frequently desire more information than just the production plan itself. One question that is often asked is, “For any given shipment in the production plan, which resources were utilized specifically to enable that shipment?” Generally, this information is not evident in the production plan itself. The production plan specifies which resources are used and which demands are met, but it does not provide an association between the two. This may be called “the pegging problem” for RCPP; that is, given an RCPP problem and a corresponding feasible production plan, define an association between the individual resources that are utilized in the plan and the individual shipments in the plan. Such an association is called a “pegging” of the production plan. A resource that is associated with a particular shipment is said to be “pegged” to it.
Users of RCPP systems have many uses for a pegging of a production plan, including the following:                Verifying the validity of the production plan.        Verifying the validity of the input data.        Identifying which demands are responsible for depleting the supplies of critical (i.e., bottleneck) resources.        Identifying opportunities to improve the production plan by increasing the supplies of the resources that were used by the most important demands.        Generally deepening the user's understanding of the production plan.        
One possible method for computing a pegging might be called “Pegging By Monitoring”. This technique would apply when the RCPP system solves the RCPP problem by an “incremental allocation” technique, as disclosed for example in U.S. Pat. No. 5,548,518. An incremental allocation technique for RCPP has the following key properties:                It starts with an empty production plan.        It proceeds by iterations.        Each iteration creates only one new shipment.        As the technique progresses, the production volume for any product in any period can be increased, but it can never be decreased.The “Pegging By Monitoring” technique would proceed by monitoring the incremental allocation technique; that is, whenever a production volume of a product is increased by the incremental technique, that increase is pegged to the shipment for the current iteration.        
In some respects, “Pegging By Monitoring” is a very appealing form of pegging. It s a direct reflection of what how the production plan was built up by the incremental allocation technique. But it has the following drawbacks:                It can only be applied, if the production plan is being computed by an incremental allocation technique.        It must be integrated with the RCPP solver itself; it cannot be applied to a production plan that has already been computed.        